Computer Programming N-Queens Problem এবং Maze Solving গাইড ও নোট

N-Queens Problem এবং Maze Solving

N-Queens Problem এবং Maze Solving দুটি ক্লাসিক সমস্যা যা ব্যাকট্র্যাকিং (Backtracking) অ্যালগরিদম ব্যবহার করে সমাধান করা যেতে পারে। ব্যাকট্র্যাকিং একটি পদ্ধতি যা সম্ভাব্য সমাধান অনুসন্ধান করে এবং যেকোনো সময় যদি একটি সমাধান সঠিক না হয়, তখন সেটি পরিত্যাগ করে অন্য সম্ভাবনা খোঁজে।

১. N-Queens Problem

N-Queens Problem একটি গ্রিডে Nটি কুইন বসানোর সমস্যা, যেখানে কুইনগুলোর মধ্যে একে অপরকে আক্রমণ করতে পারবে না। অর্থাৎ, কোন দুটি কুইন একে অপরকে সারি, কলাম বা ডায়াগনালে আক্রমণ করতে পারবে না। এই সমস্যা সমাধানে ব্যাকট্র্যাকিং অ্যালগরিদম ব্যবহার করা হয়।

N-Queens Problem এর সমাধান পদ্ধতি:

1. একটি N x N গ্রিড তৈরি করা হয়।
2. প্রথম কলাম থেকে কুইন বসানো শুরু করা হয় এবং প্রতিটি কুইন বসানোর সময় চেক করা হয় যে তা অন্যান্য কুইনদের আক্রমণ করতে পারবে কি না।
3. যদি কোনো কুইন বসানো সম্ভব না হয়, তবে ব্যাকট্র্যাকিং করা হয় (পূর্ববর্তী কুইনটি সরিয়ে নতুন অবস্থানে বসানো হয়)।
4. যদি সফলভাবে Nটি কুইন বসানো যায়, তবে সমাধান পাওয়া যায়।

সি প্রোগ্রামে N-Queens Problem এর ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdbool.h>

#define N 8

// একটি ফাংশন যা বোঝাবে একটি নির্দিষ্ট কলাম থেকে কুইন বসানো যাবে কিনা
bool isSafe(int board[N][N], int row, int col) {
    // একে অপরকে আক্রমণ না করার জন্য সারি, কলাম এবং ডায়াগনাল পরীক্ষা করা
    for (int i = 0; i < col; i++) {
        if (board[row][i] == 1) return false;
    }

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) return false;
    }

    for (int i = row, j = col; j >= 0 && i < N; i++, j--) {
        if (board[i][j] == 1) return false;
    }

    return true;
}

// ব্যাকট্র্যাকিং ফাংশন
bool solveNQueens(int board[N][N], int col) {
    if (col >= N) return true; // সমস্ত কুইন বসানো হয়ে গেলে

    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1; // কুইন বসান

            if (solveNQueens(board, col + 1)) {
                return true; // সফলভাবে সমাধান পাওয়া গেছে
            }

            board[i][col] = 0; // ব্যাকট্র্যাকিং
        }
    }

    return false; // সমাধান সম্ভব না হলে
}

// কুইন বসানো দেখানোর জন্য ফাংশন
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int board[N][N] = {0};

    if (solveNQueens(board, 0)) {
        printSolution(board);
    } else {
        printf("No solution exists\n");
    }

    return 0;
}

ব্যাখ্যা:

1. isSafe() ফাংশনটি চেক করে যে একটি কুইন নির্দিষ্ট সারি ও কলামে বসানো যাবে কি না।
2. solveNQueens() ফাংশনটি ব্যাকট্র্যাকিংয়ের মাধ্যমে সমস্ত কুইন বসানোর চেষ্টা করে।
3. printSolution() কুইনগুলি বসানোর পরে তাদের সমাধান প্রদর্শন করে।

২. Maze Solving Problem

Maze Solving একটি ক্লাসিক সমস্যা যেখানে একটি মেজ (পথ) থেকে একটি নির্দিষ্ট পয়েন্ট (এন্ট্রান্স) থেকে অন্য পয়েন্ট (এক্সিট) পর্যন্ত পৌঁছানোর উপায় খুঁজে বের করা হয়। এটি সাধারণত একটি 2D মেট্রিক্সে উপস্থাপন করা হয় যেখানে বিভিন্ন কোষের মান হয়:

• 0: খালি জায়গা (যেখানে চলাচল করা যায়)
• 1: বাধা (যেখানে চলাচল করা যায় না)

মেজ সলভিং সমস্যার সমাধানে ব্যাকট্র্যাকিং বা DFS (Depth First Search) ব্যবহার করা হয়।

Maze Solving এর সমাধান পদ্ধতি:

1. মেজের শুরুর পয়েন্ট থেকে একটি রিকার্সিভ ফাংশন কল করা হয়।
2. প্রতিটি কোষের জন্য পরীক্ষা করা হয়, যদি কোষটি পাসযোগ্য (0) হয়, তাহলে সেখানে যেতে হবে।
3. যদি কোষটি ভিজিট করা হয়ে থাকে বা বাধা থাকে, তাহলে ব্যাকট্র্যাকিং করা হয় এবং অন্য পথে যাওয়ার চেষ্টা করা হয়।
4. এক্সিট পয়েন্টে পৌঁছালে সমাধান পাওয়া যায়।

সি প্রোগ্রামে Maze Solving এর ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdbool.h>

#define N 4

// মেজের কোষে চলার জন্য নির্দেশিকা
int rowNum[] = {-1, 1, 0, 0};
int colNum[] = {0, 0, -1, 1};

// মেজ সলভিং ফাংশন
bool isSafe(int maze[N][N], int x, int y, bool visited[N][N]) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0 && !visited[x][y]);
}

bool solveMazeUtil(int maze[N][N], int x, int y, bool visited[N][N]) {
    // এক্সিট পয়েন্টে পৌঁছালে সমাধান পাওয়া যাবে
    if (x == N - 1 && y == N - 1) {
        visited[x][y] = true;
        return true;
    }

    // যদি চলা সম্ভব হয়
    if (isSafe(maze, x, y, visited)) {
        visited[x][y] = true;  // কোষটি ভিজিট করা হয়েছে

        // উপরে চলা
        if (solveMazeUtil(maze, x - 1, y, visited)) return true;

        // নিচে চলা
        if (solveMazeUtil(maze, x + 1, y, visited)) return true;

        // বাম দিকে চলা
        if (solveMazeUtil(maze, x, y - 1, visited)) return true;

        // ডান দিকে চলা
        if (solveMazeUtil(maze, x, y + 1, visited)) return true;

        visited[x][y] = false;  // ব্যাকট্র্যাকিং
        return false;
    }

    return false;
}

void printSolution(bool visited[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", visited[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int maze[N][N] = {
        {0, 1, 0, 0},
        {0, 1, 0, 1},
        {0, 0, 0, 0},
        {1, 1, 0, 0}
    };
    bool visited[N][N] = {false};

    if (solveMazeUtil(maze, 0, 0, visited)) {
        printf("Solution found:\n");
        printSolution(visited);
    } else {
        printf("No solution exists\n");
    }

    return 0;
}

ব্যাখ্যা:

1. isSafe() ফাংশনটি চেক করে যে একটি নির্দিষ্ট কোষটি পাসযোগ্য (0) এবং আগে ভিজিট করা হয়নি।
2. solveMazeUtil() ফাংশনটি রিকার্সিভভাবে মেজের মধ্যে চলাচল করে এবং এক্সিট পয়েন্টে পৌঁছানোর চেষ্টা করে।
3. visited[][] অ্যারে ব্যাকট্র্যাকিংয়ের জন্য ব্যবহৃত হয়, যাতে কোষ পুনরায় ভিজিট না হয়।

সারসংক্ষেপ

1. N-Queens Problem: একটি নির্দিষ্ট আকারের গ্রিডে Nটি কুইন বসানোর সমস্যা যেখানে কুইনগুলি একে অপরকে আক্রমণ করতে পারে না। এটি ব্যাকট্র্যাকিং ব্যবহার করে সমাধান করা হয়।
2. Maze Solving: একটি মেজ (পথ) সমাধানের সমস্যা যেখানে শুরুর পয়েন্ট থেকে এক্সিট পয়েন্টে পৌঁছানোর পথ খোঁ

জা হয়। এটি ব্যাকট্র্যাকিং বা DFS পদ্ধতি ব্যবহার করে সমাধান করা হয়।

ব্যাকট্র্যাকিংয়ের মাধ্যমে উভয় সমস্যাই কার্যকরভাবে সমাধান করা যায়, কারণ এটি সম্ভাব্য সমাধানগুলো পরীক্ষার মাধ্যমে সঠিক সমাধান খুঁজে বের করে।